package com.leetcode.array_matrix;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/9/8 22:16
 */
public class LongestConsecutive_128 {

    // 核心是操作引用，可以将之前相连的序列同时增加
    public int longestConsecutive(int[] nums) {
        // 之所以用数组，是为了保证这个变量可以相邻序列被共享
        Map<Integer, int[]> map = new HashMap<>();

        int max = 0;

        for (int num : nums) {
            if (map.containsKey(num)) {
                continue;
            }

            if (map.containsKey(num - 1) && map.containsKey(num + 1)) {
                // 如果num的左右都存在值，那么将左半部分的值与右半部分相加，再加一
                map.get(num - 1)[0] += map.get(num + 1)[0] + 1;
                // 把这个值的引用赋给右半相连的部分
                map.put(num, map.get(num - 1));
                int temp = num + 1;
                while (map.containsKey(temp)) {
                    map.put(temp++, map.get(num - 1));
                }
            } else if (map.containsKey(num - 1)) {
                map.get(num - 1)[0]++;
                map.put(num, map.get(num - 1));
            } else if (map.containsKey(num + 1)) {
                map.get(num + 1)[0]++;
                map.put(num, map.get(num + 1));
            } else {
                // 只需要用一个单长度数组即可，重点是共享引用
                map.put(num, new int[]{1});
            }

            max = Math.max(max, map.get(num)[0]);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {-4, -1, 4, -5, 1, -6, 9, -6, 0, 2, 2, 7, 0, 9, -3, 8, 9, -2, -6, 5, 0, 3, 4, -2};

        LongestConsecutive_128 ans = new LongestConsecutive_128();

        System.out.println(Arrays.toString(arr));

        System.out.println(ans.longestConsecutive(arr));
    }
}
